from uf import UF
from collections import defaultdict
from time import time

t0 = time()

with open("clustering2.txt", 'r') as f:
    data=[map(int, line.split()) for line in f]

t1 = time()

firstline = data.pop(0)
totalnode = firstline[0]
numofbits = firstline[1]

def inode(list):
    node = 0
    for x in list:
        node = node*2+x
    return node

def hammingdis(p,q):
    dis=0
    z = p^q
    while(z):
        dis += 1
        z &= z-1
    return dis
def hamming(p,q):
    dis=0
    for i in range(len(p)):
        if (p[i] != q[i]):
            dis += 1
    return dis

myuf = UF(totalnode)
mydict = defaultdict(list)
flag = [0]*totalnode


for i in range(totalnode):
    node = inode(data.pop(0))
    data.append(node)
    mydict[node].append(i)


for i in range(totalnode):
    c = mydict.get(data[i])
    # 0
    if(len(c) > 1):
        d = [elem for elem in c if elem != i]
        for elem in d:
            myuf.weighted_union(i,elem)
    # 1
    for k in range(numofbits):
        firstrange = data[i] ^ (1<<k)
        if( mydict.get(firstrange) != None):
            for elem in mydict.get(firstrange):
                myuf.weighted_union(i,elem)

    # 2
    for k in range(numofbits):
        for j in range(k+1,numofbits):
            secondrange = data[i]^(1<<k)^(1<<j)
            if (mydict.get(secondrange) != None):
                for elem in mydict.get(secondrange):
                    myuf.weighted_union(i,elem)

t3 = time()

print myuf.curCluster()
print 'load file takes %f' %(t1-t0)
print 'get the result takes %f' %(t3-t1)
